package com.zq.solution.listnode;

/**
 * @ClassName InsertionSortList
 * @Description
 * 147. 对链表进行插入排序
 * 插入排序算法：
 *   插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 *   每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 *   重复直到所有输入数据插入完为止。
 * 示例 1：
 *   输入: 4->2->1->3
 *   输出: 1->2->3->4
 * @Author ZQ
 * @Date 2020/11/20 8:51
 * @Version 1.0
 */
public class InsertionSortList {
    public ListNode<Integer> insertionSortList(ListNode<Integer> head) {
        if (head == null) return head;
        ListNode<Integer> dummyHead = new ListNode<>(0);
        dummyHead.next = head;
        ListNode<Integer> lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode<Integer> prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}
